/*
** 3518.c
** 
** Made by (seakage2h)
** Login   <seakage2h@seakage2h-ubuntu>
** 
** Started on  Sat Sep 13 20:05:19 2008 seakage2h
** Last update Sun May 12 01:17:25 2002 Speed Blue
*/

/* #include "3518.h" */
#include <stdio.h>

int main()
{
     int p[100000];		/* store the prime numbers */
     p[99999] = 1299709;	/* we have the number */
     
     int can;			/* prime number candidate */
     int pos;			/* the last computed prime number
				 * array index */
     static int isprime;
     int req;
     
     int i, j;
     /* preload the first prime numbers */
     p[0] = 2, p[1] = 3, p[2] = 5, p[3] = 7, p[4] = 11, p[5] = 13;
     p[6] = 17, p[7] = 19, p[8] = 23, p[9] = 29, p[10] = 31;

     pos = 11;			/* set position */

     for (i = 32; i < 1299708; i++){
	  isprime = 1;
	  for (j = 0; p[j] * p[j] <= i; j++)
	       if (i % p[j] == 0){
		    isprime = 0;
		    break;
	       }
	  if (isprime)
	       p[pos++] = i;
     }

     while(1){
	  scanf("%d", &req);
	  if (req == 0) break;
	  for (j = 0; p[j] < req; j++);
	  if (req == p[j])
	       printf("%d\n", 0);
	  else printf("%d\n", p[j] - p[j-1]);
     }
	       
     return 0;
}

